package org.chnxi.datastructures.stack;

import java.util.List;

/**
 * 中缀表达式
 * 不支持小括号，第一位不能是符号位，如：-7+2或(1+2)*3
 * 前缀表达式：
 * 特点：从右向左扫描表达式，遇到数字时，将数字压入栈，遇到预算符时弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈，
 * 重复上述过程，直到表达式最左端，最后运算得出的值即为表达式的结果。
 * 后缀表达式：
 * 特点：从左向右扫描表达式，遇到数字时，将数字压入栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈，
 * 重复上述过程，直到表达式最右端，最后运算得出的值即为表达式结果。
 */
public class Calculator {
    public static void main(String[] args) {
        String exp = "7*2*2-5+1-5+3-4";

        Calculator c = new Calculator();
        int result = c.getResult(exp);
        System.out.println(exp+"="+result);
    }

    //存放数字
    private ListStack<Integer> numStack = new ListStack<>();
    //存放操作符
    private ListStack<Integer> operStack = new ListStack<>();

    public Integer getResult(String expre){
        char[] chars = expre.toCharArray();
        int i = 0;
        String keepNum = "";
        while (true){
            char c = chars[i];
            if(isOpr(c)){ //如果是运算符号
                if(!operStack.isEmpty()){ //如果符号栈不为空，需要比较符号优先级

                    if(priority(c) <= priority(operStack.peek())){
                        int num1 = numStack.pop();
                        int num2 = numStack.pop();
                        int oper = operStack.pop();
                        int result = cal(num1 , num2 , oper);
                        System.out.println("num1 = "+ num1+";num2="+num2+";oper="+String.valueOf((char)oper)+";result="+result);
                        numStack.push(result);
                        operStack.push((int)c);
                    }else{
                        operStack.push((int)c);
                    }
                }else{ //直接入栈
                    operStack.push((int)c);
                }
            }else{
                keepNum+=c;
                if(i>= expre.length()-1 || isOpr(chars[i+1])){
                    numStack.push(Integer.parseInt(keepNum));
                    keepNum = "";
                }
            }
            i++;
            if(i >= expre.length()){
                break;
            }
        }

        while (!operStack.isEmpty()){
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int oper = operStack.pop();
            int result = cal(num1 , num2 , oper);
            System.out.println("num1 = "+ num1+";num2="+num2+";oper="+String.valueOf((char)oper)+";result="+result);
            numStack.push(result);
        }
        return numStack.pop();
    }

    public int priority(int oper){
        if(oper == '*' || oper == '/'){
            return 1;
        }else if(oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1;
        }
    }

    public boolean isOpr(char val){
        return val == '*' || val == '/' ||val == '+' ||val == '-';
    }

    public int cal(int num1 , int num2 , int oper){
        int res = 0;
        switch (oper){
            case '+' :
                res = num1 + num2;
                break;
            case '*' :
                res = num1 * num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '/':
                res = num2 / num1;
            default:
                break;
        }
        return res;
    }
}
